#include <iostream>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x)
		:val(x)
		, left(nullptr)
		, right(nullptr)
	{}
	TreeNode(int x,TreeNode* _left,TreeNode* _right)
		:val(x)
		,left(_left)
		,right(_right)
	{}
};

class Solution 
{
public:
	TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)
	{
		if (t1 == nullptr)
			return t2;
		if (t2 == nullptr)
			return t1;
		TreeNode* head = new TreeNode(t1->val + t2->val);
		head->left = mergeTrees(t1->left, t2->left);
		head->right = mergeTrees(t1->right, t2->right);

		return head;
	}
};
void InOrder(TreeNode* root)
{
	if (root==nullptr)
	{
		return;
	}
	InOrder(root->left);
	cout << root->val << " ";
	InOrder(root->right);
}
int main()
{
	//{1,3,2,5},{2,1,3,#,4,#,7}
	TreeNode* C1 = new TreeNode(5);
	TreeNode* A1 = new TreeNode(3, C1, nullptr);
	TreeNode* B1 = new TreeNode(2);
	TreeNode* root1 = new TreeNode(1, A1, B1);

	TreeNode* C2 = new TreeNode(4);
	TreeNode* D2 = new TreeNode(7);
	TreeNode* A2 = new TreeNode(1, nullptr, C2);
	TreeNode* B2 = new TreeNode(3, nullptr, D2);
	TreeNode* root2 = new TreeNode(2, A2, B2);

	Solution xz;
	TreeNode* cur = xz.mergeTrees(root1, root2);

	InOrder(cur);

	return 0;
}